/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
// 基础解法，双指针方法
var isSubsequence = function (s, t) {
  let sIndex = 0;
  let tIndex = 0;

  while (sIndex < s.length && tIndex < t.length) {
    if (s[sIndex] === t[tIndex]) {
      sIndex++;
    }
    tIndex++;
  }

  return sIndex === s.length;
};

// 进阶解法：预处理主串 + 二分查找
function createLookup(t) {
  const lookup = new Map();
  for (let i = 0; i < t.length; i++) {
    const char = t[i];
    if (!lookup.has(char)) {
      lookup.set(char, []);
    }
    lookup.get(char).push(i);
  }
  return lookup;
}

function isSubsequenceAdvanced(s, t, lookup) {
  let prev = -1;
  for (const char of s) {
    if (!lookup.has(char)) {
      return false;
    }
    const indices = lookup.get(char);
    // 二分查找第一个大于 prev 的索引
    let left = 0, right = indices.length - 1;
    let res = -1;
    while (left <= right) {
      const mid = Math.floor((left + right) / 2);
      if (indices[mid] > prev) {
        res = indices[mid];
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    if (res === -1) {
      return false;
    }
    prev = res;
  }
  return true;
}

// 进阶使用示例
const t = "abcde";
const lookup = createLookup(t);
console.log(isSubsequenceAdvanced("ace", t, lookup)); // true
console.log(isSubsequenceAdvanced("aec", t, lookup)); // false